从0打卡leetcode之day 5 ---两个排序数组的中位数

发表于 | 分类于 | 0 comments | 浏览 次

前言

我靠，才坚持了四天，就差点不想坚持了。不行啊，我得把leetcode上的题给刷完，不然怕是不好进入bat的大门。

题目描述

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。
请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。你可以假设 nums1 和 nums2 均不为空。

示例
1
2
3
4
nums1 = [1, 3]
nums2 = [2]

中位数是 2.0
1
2
3
4
nums1 = [1, 2]
nums2 = [3, 4]

中位数是 (2 + 3)/2 = 2.5``

解题

最简单粗暴的就是把这两个数组头尾连接起来，然后重新给他们排序一下，冒泡排序相信你信手拈来，当然，你也可以装逼用快速排序。

但是，如果这样子做的话，题目给你的有序数组就没啥用了，和无序一个样，所以这样做是不行的。题目要求是时间复杂度不能超过O(log(n+m))，说实话，这个复杂度我是不知道怎么做好，我的做法时间复杂度是O(n+m)。

具体是这样的

居然两个数组都是有序的了，我们可以再弄一个中间数组，然后把两个数组各自从数组头开始比较，哪个元素小，我们就把它存在中间数组。然后接下下一个元素一直比较下去。

我还是直接上代码吧。如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int t = m + n;//总长度
        int temp[] = new int[t];
        int i  = 0, j = 0, k = 0;
        double obj;//用来存目标值

        while(i < m && j < n){
            //把数组中比较小的值转移到temp数组中
            if(nums1[i] < nums2[j]){
                temp[k++] = nums1[i++];
            }else{
                temp[k++] = nums2[j++];
            }
        }
        //把剩余的转移过去
    while (i < m){
            temp[k++] = nums1[i++];
    }
    while(j < n){
            temp[k++] = nums2[j++];
    }
    //两个数组的总个数是奇数还是偶数
    if(t % 2 == 0){//偶数
            obj = (temp[t/2] + temp[(t-1)/2]) / 2.0;
    }else{
            obj = temp[t/2];
    }

    return obj;
}

虽然时间复杂度是O(n+m)，但是提交的时候居然通过了，而且还打败了93%的人。

不过，这里还可以在优化，把时间复杂度降低到O((n+m)/2)。
就是说其实我们不用给整个temp数组排序，我们只要求出前面一半的数组元素就可以知道中间那个元素了，。例如不管一共是偶数个元素还是奇数个元素，我们让temp存到下标为t/2就可以了。然后再来判断t是奇数还是偶数…..

例如上面两个示例，示例1一共有三个元素，那么temp[t/2]=temp[1]=2。然后直接把temp[t/2]=temp[1]取出来返回就可以了。

示例2一共有4个元素，那么temp[t/2]=temp[2]=3。由于是偶数，我们直接把temp[t/2]=3和temp[t/2-1]=2这两个元素取出来处理之后返回就可以了。

至于代码这么写，我就不写了。知道有这么一回事就可以了。

如果你坚持想要O(log(n+m))的时间复杂度，那么可以看官方给的答案：

答案解析

完